package com.cdream.basic.algorithm.leetcode.linkedlist;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author cdream
 * @date 9/8/21
 */
public class Question502 {
    public static void main(String[] args) {
        new Question502().findMaximizedCapital(2,0,new int[]{1,2,3},new int[]{0,1,1});
    }
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int[][] cp = new int[profits.length][2];
        for (int i = 0; i < profits.length; i++) {
            cp[i][0] = capital[i];
            cp[i][1] = profits[i];
        }
        Arrays.sort(cp, Comparator.comparingInt(a -> a[0]));

        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        int curr = 0;
        for (int i = 0; i < k; i++) {
            // 在当前项目不超标的情况下，成本低于总成本的项目加进队列
            while (curr<profits.length && cp[curr][0]<=w){
                pq.add(cp[curr][1]);
                curr++;
            }
            if (!pq.isEmpty()){
                // 选个最大的
                w+=pq.poll();
            }else{
                break;
            }
        }
        return w;
    }
}
